home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / x11 / strategy / xsok-1.000 / xsok-1 / xsok-1.01 / solver / BFS.c next >
C/C++ Source or Header  |  1994-11-24  |  4KB  |  128 lines
  1. #include <stdio.h>
  2. #include "BFS.h"
  3. #include "crc16.h"
  4.  
  5. #define STATISTICS
  6.  
  7. static struct BFS bfs;
  8.  
  9. #ifdef STATISTICS
  10. static unsigned long searches, misses;
  11. #endif
  12.  
  13. void BFS_init(size_t keylength, size_t datalength, int hashbits,
  14.           unsigned long ndata, int backtrack) {
  15.     if (hashbits < 9 || hashbits > 24)
  16.     fatal("only 9..24 bits hashsize allowed!");
  17.     /* copy args */
  18.     bfs.keylength = keylength;
  19.     bfs.datalength = datalength;
  20.     bfs.hashbits = hashbits;
  21.     bfs.ndata = ndata;
  22.     /* compute rest */
  23.     bfs.ptrsize = (hashbits+7) >> 3;
  24.     bfs.hashmask = (1UL << hashbits) - 1UL;
  25.     bfs.totallength = bfs.datalength;
  26.     if (backtrack)
  27.     bfs.totallength += bfs.ptrsize;
  28.     bfs.level = 0;
  29.     if (ndata >= bfs.hashmask)
  30.     fatal("BFS: cannot hold that much data\n");
  31.     printf("BFS memory usage:\n%ld byte for hashtable\n%ld byte for data\n",
  32.        bfs.ptrsize * bfs.hashmask, bfs.ndata * bfs.totallength);
  33.     bfs.hashtable = malloc_(bfs.ptrsize * bfs.hashmask + 2); /* 2 for trick */
  34.     memset(bfs.hashtable, 0xff, bfs.ptrsize * bfs.hashmask); /* free hash */
  35.     bfs.data = malloc_(bfs.ndata * bfs.totallength);
  36.     bfs.endhash = bfs.hashtable + bfs.ptrsize * bfs.hashmask;
  37.     bfs.read = 0;
  38.     bfs.write = 0;
  39.     bfs.stop = 0;
  40. }
  41.  
  42. int BFS_retrieve(void *data) {
  43.     if (bfs.read == bfs.stop)
  44.     return 0;
  45.     memcpy(data, bfs.data + bfs.totallength * bfs.read++, bfs.datalength);
  46.     return 1;
  47. }
  48.  
  49. int BFS_newlevel(void) {
  50.     if (bfs.stop == bfs.write)
  51.     return 0;    /* no items were stored in this level */
  52.     /* if (bfs.read == bfs.stop), the old level has been read out completely */
  53.     bfs.read = bfs.stop;
  54.     bfs.stop = bfs.write;
  55. #ifdef STATISTICS
  56.     printf("%6ld items stored at level %3d (%6lu total), "
  57.        "(%ld searches, %ld misses)\n", bfs.stop - bfs.read,
  58.        bfs.level, bfs.write, searches, misses);
  59.     searches = 0;
  60.     misses = 0;
  61. #endif
  62.     ++bfs.level;
  63.     return 1;
  64. }
  65.  
  66. long BFS_store(void *data) {
  67.     unsigned long hashcode;
  68.     unsigned char *ptr;
  69.  
  70. #ifdef STATISTICS
  71.     ++searches;
  72. #endif
  73.     CRC16_reset();
  74.     hashcode = ((unsigned long)CRC16_add(data, bfs.keylength) << (bfs.hashbits-16))
  75.     & bfs.hashmask;
  76.     ptr = bfs.hashtable + bfs.ptrsize * hashcode;
  77.     /* printf("searching code %x\n", hashcode); */
  78.     /* search a free entry in the hashtable */
  79.     for (;;) {
  80.     unsigned long entrynr;
  81.     if (ptr == bfs.endhash)        /* wrap around */
  82.         ptr = bfs.hashtable;
  83.     entrynr = ((unsigned long)ptr[0] | ((unsigned long)ptr[1] << 8)
  84.          | ((unsigned long)ptr[2] << 16)) & bfs.hashmask;
  85.     if (entrynr == bfs.hashmask)
  86.         break;            /* found a free entry */
  87.     if (!memcmp(bfs.data+bfs.totallength*entrynr, data, bfs.keylength)) {
  88.         /* merge the entries */
  89.         return (long)entrynr;
  90.     }
  91. #ifdef STATISTICS
  92.     ++misses;
  93. #endif
  94.     ptr += bfs.ptrsize;
  95.     }
  96.  
  97.     /* there was no matching entry => create a new one */
  98.     if (bfs.write == bfs.ndata)
  99.     fatal("BFS: data table full\n");
  100.     ptr[0] = (unsigned char)bfs.write;
  101.     ptr[1] = (unsigned char)(bfs.write >> 8);
  102.     if (bfs.hashbits > 16)
  103.     ptr[2] = (unsigned char)(bfs.write >> 16);
  104.  
  105.     ptr = bfs.data+bfs.totallength*bfs.write;
  106.     memcpy(ptr, data, bfs.datalength);
  107.     if (bfs.totallength > bfs.datalength) {
  108.     /* now store the backtrack-pointer */
  109.     ptr += bfs.datalength;
  110.     ptr[0] = (unsigned char)bfs.read;
  111.     ptr[1] = (unsigned char)(bfs.read >> 8);
  112.     if (bfs.hashbits > 16)
  113.         ptr[2] = (unsigned char)(bfs.read >> 16);
  114.     }
  115.     return (long)(bfs.write++);
  116. }
  117.  
  118. long BFS_getentry(long entrynr, void *data) {
  119.     unsigned char *ptr = bfs.data + bfs.totallength * entrynr;
  120.     memcpy(data, ptr, bfs.datalength);
  121.     if (bfs.totallength == bfs.datalength)
  122.     return -1L;
  123.     ptr += bfs.datalength;
  124.     entrynr = ((long)ptr[0] | ((long)ptr[1] << 8)
  125.          | ((long)ptr[2] << 16)) & bfs.hashmask;
  126.     return entrynr - 1L;
  127. }
  128.